1. Field of the Invention
The present invention relates to methods for software inspection and verification and, more specifically, in one embodiment to methods for improving coherency by ensuring atomicity in runtime integrity measurements.
2. Description of the Related Art
Recent work in software integrity verification has expanded the scope of measurement collection from static load time images to running process states. Runtime integrity measurement relies on the ability of a measurement agent (MA) to observe the memory image of a running process and to construct some meaningful description of the process's current state. Both load time and runtime measurements may be evaluated by a remote appraiser as part of an access control decision. However, because runtime measurements represent fresher assertions about the target's state, one can have more confidence that decisions that include runtime measurements reflect the intent of the system owner than decisions which rely solely on load time measurements.
In some systems, a runtime measurement may consist of a cryptographic hash of critical but (presumably) static regions of the target's memory. Other systems include more complex characterizations of the target's dynamic state. No matter what technique is used it is vital that the measurement be meaningful and correct.
Unlike in load time measurement architectures, the target of a runtime measurement is running and, hence, able to change its state. In this setting, a proper measurement must reflect a coherent state of the target. This coherency property can be divided into two distinct properties which must be satisfied to obtain a coherent measurement. Atomicity requires the measurement to reflect the state of the target at a particular moment in time. Quiescence asserts that the target data is in a consistent state, i.e. not a critical section.
Without ensuring coherency of measurement, both false positive and negative results may ensue. In the former case, a failed measurement may mean unwarranted denial-of-service to the target, unnecessary rebooting, or manual inspection. Perhaps more dangerous is the latter case, where a compromised system may go undetected and continue to run, and exploit other systems that rely on the correctness of measurement. To elucidate the coherency problem, consider the effects of coherency on two example integrity measurements.
In a simple example, a system tracks two bits of information, a and b, and maintains a parity bit p. Integrity is measured by the assertion a xor b=p (i.e., the parity bit must accurately reflect the parity of the first two bits). Suppose an attacker can manipulate any of the three bits during measurement. The two parts of the coherency problem are as follows, illustrating false negative and false positive results, respectively.                Atomicity: Suppose the system starts in a bad state: 0, 1, 0. However, measurement might read the first bit, after which the attacker could switch the state to 1, 0, 0, and measurement will see 0, 0, 0 and the state is considered valid.        Quiescence: Suppose the system begins updating the state from 0,0,0 to 1,0, 1. Measurement is done between the two updates at 1,0,0 and runs to completion before the parity bit is updated. The state is therefore considered invalid.        
This simple example demonstrates the necessity of coherent measurement. Failing to enforce either the atomicity or quiescence property may result in an incorrect measurement. Further, as the complexity of measurement increases, the challenge of maintaining coherency becomes more difficult, and the potential impact on the target becomes greater. Consider the following, more complex example.
A system maintains two distinct circular doubly-linked lists: in_use_list and free_list. Integrity is measured by the assertion that all elements of in_use_list have a particular flag set and elements of free_list do not. Further, there is an implicit assertion that in_use_list and free_list form distinct valid circular doubly-linked lists. The MA must walk both lists and record or validate the proposition.                Atomicity: Suppose the system starts in a bad state, where an element of in_use_list does not have the correct flag set. Measurement may finish correctly on free_list, yet before in_use_list is measured, the bit is flipped, causing measurement to be considered valid.        Quiescence: Suppose the system starts in a valid state, where both lists are valid and have the proper bits set. Suppose the measurement occurs after the target begins updating the lists, moving an element from free_list to in_use_list. Depending on when measurement takes place, one of the lists may not even be a valid circular doubly-linked list, if the pointers are in the process of changing. This may cause measurement to fail, even though the system is valid in both the prior state and the new state after the update.        
This example further emphasizes the importance of coherency of measurement. Measurement must avoid the danger of an attacker changing things during measurement to escape detection. The quiescence failure in this example illustrates the fragility of runtime measurement; measurement must be done carefully to avoid measuring a target when the target is in a critical section.
A failure of atomicity is more relevant for false negatives than false positives. A false positive would mean that the system is valid at the beginning of measurement, and becomes bad during measurement. From the perspective of the point in time of measurement, reporting a bad measurement in this case is a false positive, since the state was valid at the point of the measurement. However, reporting this bad measurement at this point can hardly be considered a bad thing; in any case, an atomic measurement would not capture this invalid state, since it occurs after the point in time of measurement.
While not part of coherency, related goals of measurement are minimizing runtime overhead and avoiding target realization of measurement. A complete solution to the coherency problem will:                Ensure measurement reflects the state of the target at a single moment in time (Atomicity);        Ensure target data is in a consistent state at measurement time (Quiescence);        Maximize target performance without starving the MA; and        Be undetectable from the target/not require target participation.        
Load-time measurement systems implicitly meet the coherency goal because the target of measurement is not actively modifying its state while the measurement is being performed. For example, one system hashes the file system image of key objects (such as system executables) as they are loaded by the operating system kernel. Because the measurement is performed before the image is actually executed, there is no chance that the image is in an inconsistent state.
The problem is the atomicity property for run-time measurement agents. Naive approaches can accurately enforce the atomicity property, but exact undesirable performance penalties on the target.
Pausing the target during measurement will not allow the target to update any of its memory, thus making the measurement atomic. However, this has the undesirable effect of denial-of-service to the target for the duration of measurement, which may take several seconds. An alternative approach is to copy the entire memory of the target and perform measurement on the copies. This clearly has the side-effect of wasting large portions of memory for measurement and additionally imposing a time penalty for how long it takes to copy memory.
TABLE 1Time and Memory Overhead during Runtime MeasurementLKIMOverheadStrategyMemoryActivityRuntimeTimeMemoryPause TD256 MBIdle0.291 s166.6 ms 0 MBFUll Copy256 MBIdle0.471 s161.6 ms256 MBPause TD1024 MB Idle0.291 s165.0 ms1024 MB FUll Copy1024 MB Idle0.995 s668.4 ms1024 MB Pause TD256 MBLinux0.952 s636.8 ms 0 MBkernel buildFUll Copy256 MBLinux1.076 s178.3 ms256 MBkernel build
Table 1 above shows the time and memory overhead of the Linux Kernel Integrity Monitor (LKIM) see, e.g., P. A. Loscocco, et al., “Linux kernel integrity measurement using contextual inspection,” STC '07: Proceedings of the 2007 ACM Workshop on Scalable Trusted Computing, pp. 21-29, NY, N.Y., USA, 2007) measurement for these naive strategies for identical targets with different memory sizes and different levels of activity: either idle or building the Linux kernel. On idle targets, measurement is faster, since there is less active memory to measure. For more active targets, measurement takes longer, and can be several seconds; pausing the target for this amount of time is clearly undesirable. Further, the memory overhead for performing a full copy of memory is substantial, and can add significant downtime to the target; a full copy of a 1024 MB target takes longer to complete than the time measurement takes when pausing the target domain. (Note that the pause time of the Pause Target Domain (TD) strategy is less than the LKIM runtime due to some activity before and after the actual memory measurement.)
Given the above problems with current simple, yet naive, runtime measurement approaches it should be the objective of an inventive solution to improve coherency, and particularly atomicity, of runtime measurements without an extended denial-of-service to the target and without the need for large memory or the additional time required to copy large memory.